\documentclass[11pt]{article}
%% \topmargin -1.5cm        % read Lamport p.163
%% \oddsidemargin -0.04cm   % read Lamport p.163
%% \evensidemargin -0.04cm  % same as oddsidemargin but for left-hand pages
%% \textwidth 16.59cm
%% \textheight 21.94cm 
%$ %\pagestyle{empty}       % Uncomment if don't want page numbers
\parskip 7.2pt           % sets spacing between paragraphs
%% %\renewcommand{\baselinestretch}{1.5} % Uncomment for 1.5 spacing between lines
\parindent 0pt		 % sets leading space for paragraphs

\usepackage{fullpage}
\usepackage{listings} % For source code
\usepackage[usenames,dvipsnames]{color} % For colors and names
\usepackage[pdftex]{graphicx}
\usepackage{subfigure}
\usepackage{enumerate}

\documentclass{article}
\usepackage{amssymb,amsmath}

\newcommand{\superscript}[1]{\ensuremath{^{\textrm{#1}}}}
\newcommand{\subscript}[1]{\ensuremath{_{\textrm{#1}}}}

\definecolor{mygrey}{gray}{.96} % Light Grey
\lstset{ 
        language=[ISO]C++,              
        tabsize=3,                                                     
        basicstyle=\tiny,               
        numbers=left,                   
        numberstyle=\tiny,              
        stepnumber=2,                   
        numbersep=5pt,                  
        backgroundcolor=\color{white}, 
        %showspaces=false,              
        %showstringspaces=false,        
        %showtabs=false,                
        frame=single,                    
        tabsize=3,                          
        captionpos=b,                   
        breaklines=true,                
        breakatwhitespace=false,        
        %escapeinside={\%*}{*)},        
        commentstyle=\color{BrickRed}   
}

\title{Northeastern University \\
  Department of Computer Science \\
  - \\
  CS4740 \\
  PS3
}
\date{\today}
\author{
  Instructor: Guevera Noubir \\
  Author's Name: Paul Ozog
}

\begin{document}

\maketitle

\section{Problem 1}
\begin{enumerate}
\item If {\it any} machine that received message digests from the source gets compromised, there is the possibility that messages can be spoofed by the intruder.  Therefore, if one machine gets compromised, {\it every} machine must negotiate and update their collection of secret keys.  Also, since everyone knows the secret, the use of symmetric key crypto does not guarantee authenticity. 
\item 

  \begin{enumerate} %part 2
    \item Using openssl, the following data was determined: 
      \label{sign}
\begin{verbatim}
                    sign    sign/s
rsa  512 bits   0.000282s   3544.2
rsa 1024 bits   0.001091s    916.7
rsa 2048 bits   0.006001s    166.6
rsa 4096 bits   0.039373s     25.4
\end{verbatim}
So number of signatures sharply decreases with doubling RSA key sizes.

    \item Using openssl, the following data was determined: 
\begin{verbatim}
                  verify   verify/s
rsa  512 bits   0.000018s  54766.1
rsa 1024 bits   0.000051s  19791.9
rsa 2048 bits   0.000162s   6164.3
rsa 4096 bits   0.000554s   1804.6
\end{verbatim}
Similar to \ref{sign}), there is a sharp decrease in verifications with doubling key sizes.


    \item The signing time uses the RSA private key to decrypt.  It takes longer than the verification time because the private exponent {\it d} is much larger than the public exponent {\it e} (which typically takes a value such as 3)
      \begin{equation}
        D \left( C \right) = C ^ d mod \left( pq \right)
      \end{equation}
      vs.
      \begin{equation}
        E \left( M \right) = M ^ e mod \left( pq \right)
      \end{equation}
      {\it C\superscript{d}} is a much more intensive calculation than {\it M\superscript{e}}, so therefore signature signing takes much longer than verification.

      Message length does not matter because the output of the message digest function (say SHA1) is constant regardless of the message length.  Therefore, the sender would always be signing the same amount of data.

    \item The specs of the machine used to estimate above values are:
\begin{verbatim}
Linux paul-laptop 2.6.31-17-generic #54-Ubuntu SMP x86_64 GNU/Linux
Intel(R) Core(TM)2 Duo CPU     T6400  @ 2.00GHz
2 GB RAM
\end{verbatim}

  \end{enumerate} %end part 2

\item The sender does not need to sign every single packet.  He/she could just sign say the {\it n}th packet in a group of {\it n} packets.  This obviously means the recipients will have to wait for all {\it n} packets to arrive before the signature is verified.

\end{enumerate}


\section{Problem 2}
\begin{enumerate}
\item Yes.  An intruder {\it I} can open an authentication session to {\it B}.  After receiving message 2 containing R\subscript{2}, {\it I} does not know how to compute Hash\{K\subscript{AB},A,B,R\subscript{2}\}.  
  
  Therefore, {\it I} opens a second session to {\it B} and includes R\subscript{2} in message 1.  {\it B} replies with the value needed in the first session and {\it I} can thereby impersonate {\it A} (and continue communications assuming that {\it I} knows K\subscript{AB}).

\item One can easily fix the susceptibility to reflection attacks by forcing R\subscript{1} (the challenge to {\it B}) to be an even number and forcing R\subscript{2} (the challenge to {\it A}) to be an odd number.  That way, {\it I} can't use R\subscript{2} to challenge {\it B}. 

\item The intruder {\it I} may send a bogus message 1 to {\it B}, and use offline cracking methods to determine {\it K\subscript{AB}} in message 2 because A, B, and R\subscript{1} are all known. 

\end{enumerate}


\section{Problem 3}
\begin{enumerate}

\item
  \begin{enumerate}

    \item The decryption exponent {\it d} should satisfy
      \begin{equation}
        de \; mod \; \phi \left( n \right) = 1 \Rightarrow \boxed{d = 27}
      \end{equation}

    \item Encryption of M = 4:
      \begin{equation}
        E(4) = 4 ^3 \; mod \; (5 \times 11 ) = \boxed{9}
      \end{equation}

    \item Decryption of C = 3;
      \begin{equation}
        D(3) = 3 ^{27} \; mod \; (5 \times 11 ) = \boxed{42}
      \end{equation}

    \item Using openssl to show the two prime numbers for a typical key size of 1024:
\begin{verbatim}
prime1:
    00:ff:8f:c5:b8:8e:50:6b:0e:e1:c2:b7:6f:ef:b6:
    83:57:a1:20:bb:ef:59:cf:cb:b1:6b:95:ef:96:0e:
    09:2c:ab:7a:55:eb:1b:0d:fa:10:30:a8:76:f4:69:
    ac:1f:96:a4:cd:d5:3e:24:80:8f:f8:9a:44:8d:4f:
    eb:5c:5e:61:ad
prime2:
    00:c7:31:4b:49:d3:22:dc:58:c3:72:51:86:71:f3:
    4a:4d:0c:8a:2d:f3:81:dd:18:30:53:8a:b8:6a:9f:
    5a:ad:02:09:25:f2:fe:34:2a:06:dc:06:41:07:b4:
    08:d8:c7:4f:3b:75:62:93:43:f7:50:78:93:fa:d4:
    f2:94:42:de:99
\end{verbatim}
Each prime number is therefore 130 hexadecimal digits long, or 520 bits.  

  \end{enumerate}

\item The value of the Diffie-Hellman shared key {\it K} is given by
  \begin{equation}
    K = g^{ab}\;mod\;p \Rightarrow 2^{15}\;mod\;13 = \boxed{8}
  \end{equation}

\end{enumerate}
\section{Problem 4}
I think the main vulnerability is in message 2.  An intruder {\it I} can impersonate {\it B} and establish {\it K\subscript{AI}} with {\it A}.  Then, {\it I} can use offline guessing to get W from message 3, because {\it I} knows {\it c\subscript{1}} and {\it K\subscript{AI}}.  Even with a strong password, this is still a major vulnerability because the cracking is done offline. 

\begin{enumerate}
  \item There needs to be some sort of challenge to B in message 1.  I think the safest would be to have {\it A} and {\it B} sign their Diffie-Helman exchanges to prevent a man-in-the-middle described above.  This solution does not compromise PFS.
    
  \item Perfect Forward Secrecy (PFS) is the case that even if an attacker breaks into both {\it A} and {\it B}, he/she can't use recorded communication to decipher any encrypted information.  This assumes that neither {\it A} nor {\it B} store their private information {\it a, b, or K} after the communication session is over.

\end{enumerate}

\section{Problem 5}
\begin{enumerate}
\item For a given plaintext block {\it P\subscript{n}}, ECB always results in the same ciphertext block {\it C\subscript{n}}.  CBC, on the other hand, uses a randomn initialization vector to ensure that {\it C\subscript{n}} is not the same when {\it P\subscript{n}} is encrypted on multiple seperate occasions.  Therefore with ECB encryption, an attacker can use long-term eavesdropping to monitor trends in ciphertext blocks.

\item
  \begin{description}
    \item[Advantages of OFB compared to CBC] are as follows
      \begin{enumerate}[1.]
        \item The ``one-time pad'' between the sender and recipient can be computed in advance, before the plaintext is available.  To incorporates the one-time pad in the encryption processing involves the very fast XOR operation.  
        \item For OFB, if a block {\it C\subscript{n}} gets garbeled in the communication channel, {\it C\subscript{n+1}} will not get garbled.  CBC, on the other hand, will have a trickling effect where all ciphertext blocks after {\it C\subscript{n}} will get garbled.
        \item For CBC, entire plaintext blocks must arrive before they can be encrypted.  For OFB, the plaintext may arrive {\it bytes} at a time, and the ciphertext can be determined and transmitted without waiting for more plaintext bytes.
      \end{enumerate}
    \item[Disadvantages of OFB compared to CBC:] If an intruder knows both the plaintext and the OFB ciphertext, he can modify the ciphertext's message extremely quickly using a couple XOR operations.  Therefore, OFB can be susceptible to tampering.  
  \end{description}

\end{enumerate}

\section{Problem 6}
I'm not sure.  Here it goes: 

Since K is 64 bits long,
\begin{equation}
  K \; mod \; 2^{64} = K
\end{equation}
Therefore, if an intruder {\it I} were to be in the middle of {\it A} and {\it B}, he could feed them fake R\subscript{1}'s and R\subscript{2}'s.  Because +ing and $\oplus$ing are similar operations, {\it I} could attempt picking R\subscript{fake} such that
\begin{equation}
  K + R_{fake} = K \oplus R_{fake}
\end{equation}
If Hash(K + R\subscript{fake}) = Hash(K $\oplus$ R\subscript{fake}), {\it I} keeps these messages to give his/her offline cracking more datapoints.  Otherwise, {\it I} throws out these messages.

So, armed with multiple data points of , the attacker can  increase his chances of using an offline cracking scheme to guess K, even if Hash is by itself secure.
\end{document}
